package problem113_Path_Sum_II;

import java.util.LinkedList;
import java.util.List;

import problem108_Convert_Sorted_Array_to_Binary_Search_Tree.TreeNode;

public class Solution {
	public List<List<Integer>> pathSum(TreeNode root, int sum) {
        List<List<Integer>> result=new LinkedList<>();
        dfs(root,sum,result,new LinkedList<>());
        return result;
    }
	
	private void dfs(TreeNode node, int sum,List<List<Integer>> result,List<Integer> list){
		if(node==null) return;
		list.add(node.val);
		if(node.left==null&&node.right==null&&node.val==sum){
			result.add(new LinkedList<>(list));
		}
		dfs(node.left,sum-node.val,result,list);
		dfs(node.right,sum-node.val,result,list);
		list.remove(list.size()-1);
	}
	
	public static void main(String[] args){
		TreeNode root=new TreeNode(-2);
		root.left=null;
		root.right=new TreeNode(-3);
		System.out.println(new Solution().pathSum(root, -5));
	}
}
